package com.yangzhe.algorithm.c030;

// 数组中只有1种数出现次数少于m次，其他数都出现了m次
// 返回出现次数小于m次的那种数
// 测试链接 : https://leetcode.cn/problems/single-number-ii/
// 注意 : 测试题目只是通用方法的一个特例，课上讲了更通用的情况
public class Code06_OneKindNumberLessMtimes_LeetCode {

	public int singleNumber(int[] nums) {
		return getNumber(nums, 3);
	}

	/**
	 * 找出出现次数小于m次的数字，设这个数字是x
	 * 1. 如果每一位的数字都是0，则x的那个位一定也是0,
	 * 2. 统计每一位出现1的词频，
	 * 		如果词频是m的倍数，则x这一位是0
	 * 		如果词频不是m背书，则x这一位是1
	 */
	public int getNumber(int nums[], int m) {
		// 1.统计每一位出现1的词频
		int cntBits[] = new int[32];
		for (int i = 0; i < nums.length; i++) {
			// 这个数字的每一位都计数
			for (int j = 0; j < 32; j++) {
				// 右移j位 & 1如果是1，代表第j位是1，否则是0
				cntBits[j] += (nums[i] >> j) & 1;
			}
		}

		// 2.统计每一位出现1的词频，如果词频小于m，则说明这个数出现了次数小于m次
		int ans = 0;
		for (int i = 0; i < 32; i++) {
			// 判断词频是否是m的倍数，如果不是，则x这一位是1，把这个1放在对应的位置上
			ans |= cntBits[i] % m != 0 ? (1 << i) : 0;
		}

		return ans;
	}
}
